RSA Factoring Challenge

RSA Factoring Challenge były otwartymi zawodami zorganizowanymi przez RSA Security w celu pobudzenia badań nad praktycznymi algorytmami faktoryzacji dużych liczb. Opublikowana została lista pseudopierwszych liczb (rozkładających się na dokładnie dwa czynniki), nazwanych liczbami RSA. Za rozłożenie niektórych z nich wyznaczono pieniężną nagrodę. Najmniejsza z nich, 100-cyfrowa liczba RSA-100 została rozłożona w ciągu kilku dni, ale większość do dziś pozostaje niezłamana.

Konkurs rozpoczął się 18 marca 1991 roku, a zakończył się w maju 2007 r. Organizatorzy stwierdzili, że aktualny stan wiedzy pozwala na stosowanie bardziej zaawansowanych metod oceny siły algorytmów szyfrujących^[1].

Zawody miały na celu śledzenie rozwoju możliwości komputerów w faktoryzacji. Jest to niezwykle istotne przy wyborze długości klucza w szyfrowaniu asymetrycznym metodą RSA. Postęp w łamaniu kolejnych liczb powinien zdradzać jakie długości klucza można jeszcze uznawać za bezpieczne.

Pierwsze wygenerowane liczby RSA, od RSA-100 do RSA-500, były oznaczane według liczby cyfr dziesiętnych. Potem wprowadzono numerację zależną od liczby bitów, począwszy od RSA-576.

Zadanie

Niech $n$ oznacza liczbę RSA. Istnieją liczby pierwsze $p$ i $q,$ takie że:

n=pq.

Zadanie polega na znalezieniu tych liczb, mając dane $n$ '.

Liczby te zostały dobrane tak, aby wartości podstawowych funkcji arytmetycznych nie ułatwiały rozłożenia jej na czynniki pierwsze:

d(n)=2

\phi (n)=(p-1)(q-1)=n+1-(p+q)

\sigma (n)=(p+1)(q+1)=n+1+p+q.

Nagrody i postępy

Poniższa tabela przedstawia stan zawodów.

Wiersze różowe dotyczą liczb podanych w cyfrach dziesiętnych, wiersze żółte dotyczą liczb podanych w bitach, z wyznaczoną nagrodą za rozwiązanie.

Część nagród została wycofana ze względu na zakończenie zawodów w 2007 roku.

Liczba RSA	Cyfr	Bitów	Nagroda	Rozłożona	Zespół rozwiązujący
RSA-100	100	330	1 000 $^[2]	1 kwietnia 1991^[3]	Arjen K. Lenstra
RSA-110	110	364	4 429 $^[2]	14 kwietnia 1992^[3]	Arjen K. Lenstra i M.S. Manasse
RSA-120	120	397	5 898 $^[2]	9 czerwca 1993^[4]	T. Denny et al.
RSA-129	129	426	100 $	26 kwietnia 1994^[3]	Arjen K. Lenstra et al.
RSA-130	130	430	14 527 $^[2]	10 kwietnia 1996	Arjen K. Lenstra et al.
RSA-140	140	463	17 227 $	2 lutego 1999	Herman J. J. te Riele et al.
RSA-150	150	496		16 kwietnia 2004	Kazumaro Aoki et al.
RSA-155	155	512	9 383 $^[2]	22 sierpnia 1999	Herman J. J. te Riele et al.
RSA-160	160	530		1 kwietnia 2003	Jens Franke et al., Uniwersytet w Bonn
RSA-170	170	563		29 grudnia 2009	D. Bonenberger i M. Krone
RSA-576	174	576	10 000 $	3 grudnia 2003	Jens Franke et al., Uniwersytet w Bonn
RSA-180	180	596		8 maja 2010	S.A. Danilov i I.A. Popovyan, Uniwersytet Moskiewski
RSA-190	190	629		8 listopada 2010	A. Timofeev i I.A. Popovyan
RSA-640	193	640	20 000 $	2 listopada 2005	Jens Franke et al., Uniwersytet w Bonn
RSA-200	200	663		9 maja 2005	Jens Franke et al., Uniwersytet w Bonn
RSA-210	210	696		26 września 2013	Ryan Propper
RSA-704	212	704	30 000 $ (wycofana)	2 lipca 2012	Shi Bai, Emmanuel Thomé i Paul Zimmermann
RSA-220	220	729		13 maja 2016	S. Bai, P. Gaudry, A. Kruppa, E. Thomé i P. Zimmermann
RSA-230	230	762		15 sierpnia 2018	Samuel S. Gross, Nobilis Inc.
RSA-232	232	768		17 lutego 2020	N. L. Zamarashkin, D. A. Zheltkov i S. A. Matveev
RSA-768	232	768	50 000 $ (wycofana)	12 grudnia 2009	Thorsten Kleinjung et al.
RSA-240	240	795		2 grudnia 2019	F.Boudot, P. Gaudry, A.Guillevic, N. Heninger, E. Thomé i P. Zimmerman
RSA-250	250	829		28 lutego 2020^[5]	F.Boudot, P. Gaudry, A.Guillevic, N. Heninger, E. Thomé i P. Zimmerman
RSA-260	260	862		–
RSA-270	270	895		–
RSA-896	270	896	75 000 $ (wycofana)	–
RSA-280	280	928		–
RSA-290	290	962		–
RSA-300	300	995		–
RSA-309	309	1024		–
RSA-1024	309	1024	100 000 $ (wycofana)	–
RSA-310	310	1028		–
RSA-320	320	1061		–
...	...	...		...
RSA-450	450	1493		–
RSA-460	460	1526		–
RSA-1536	463	1536	150 000 $ (wycofana)	–
RSA-470	470	1559		–
RSA-480	480	1593		–
RSA-490	490	1626		–
RSA-500	500	1659		–
RSA-617	617	2048		–
RSA-2048	617	2048	200 000 $ (wycofana)	–

Zobacz też

liczby RSA

Przypisy

↑ RSA Laboratories, The RSA Factoring Challenge FAQ.
↑ ^a ^b ^c ^d ^e http://www.ontko.com/~rayo/primes/rsa_news.txt
↑ ^a ^b ^c RSA Honor Roll.
↑ On the factorization of RSA-120 – Springer. Springerlink.com. Retrieved on 2014-05-11.
↑ [1].Cado-nfs-discuss lista dyskusyjna.

Linki zewnętrzne

RSA Security: The new RSA factoring challenge
Eric W.E.W. Weisstein Eric W.E.W., RSA Number, [w:] MathWorld, Wolfram Research [dostęp 2020-12-13] (ang.).
Mathematica package for RSA numbers
The original challenge announcement on sci.crypt

[1] RSA Laboratories, The RSA Factoring Challenge FAQ.

[rsa-news-2] ↑ ^a ^b ^c ^d ^e http://www.ontko.com/~rayo/primes/rsa_news.txt

[honor-roll-3] RSA Honor Roll.

[4] On the factorization of RSA-120 – Springer. Springerlink.com. Retrieved on 2014-05-11.

[nfs-discussion-5] [1].Cado-nfs-discuss lista dyskusyjna.

[1]

[2]

[3]

[4]

[5]